/**
 * Created whit IntelliJ IDEA.
 * Description：
 * User：ZHONGCHEN
 * Date:2022-03-11
 * Time:11:43
 */

import com.sun.scenario.effect.impl.sw.sse.SSEBlend_SRC_OUTPeer;

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

/**
 * 2049. 统计最高分的节点数目
 * 给你一棵根节点为 0 的 二叉树 ，它总共有 n 个节点，节点编号为 0 到 n - 1 。
 * 同时给你一个下标从 0 开始的整数数组 parents 表示这棵树，其中 parents[i] 是节点 i 的父节点。
 * 由于节点 0 是根，所以 parents[0] == -1 。
 * 一个子树的 大小 为这个子树内节点的数目。每个节点都有一个与之关联的分数 。
 * 求出某个节点分数的方法是，将这个节点和与它相连的边全部 删除 ，
 * 剩余部分是若干个 非空 子树，这个节点的 分数 为所有这些子树 大小的乘积 。
 * 请你返回有 最高得分 节点的 数目 。
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/count-nodes-with-the-highest-score
 * <p>
 * 思路：在一棵树中，当把一个节点和与它相连的所有边删除，
 * 剩余部分最多为三棵非空子树，即原节点的左子树（如果有），
 * 右子树（如果有），以及把以这个节点为根结点的子树移除所形成的子树（除根结点外均有）。
 * 而这个节点的分数为这些子树的节点个数的乘积。
 * 只需实现一个方法计算以此节点为根节点的子树的大小，
 * 则其左右子树的大小可递归实现计算，再通过数学计算得到把以此节点为根节点的子树移除后的子树的大小。
 */
public class TestDemo {
    //使用两个数组保存二叉树的左右节点,索引为父节点
    static int[] right, left;
    //记录最大分数;注意溢出
    static long maxScore;
    //记录最大分数的个数
    static int cnt;
    //整颗树的大小
    static int n;

    public static int countHighestScoreNodes(int[] parents) {
        n = parents.length;
        //初始化
        right = new int[n];
        left = new int[n];
        for (int i = 0; i < n; i++) {
            right[i] = -1;
            left[i] = -1;
        }
        //构建树的表示
        for (int i = 1; i < n; i++) {
            //填充左右节点无所谓,优先填充左节点
            //left[2]==1 表示2节点的左子树为1 left[3] == -1 表示3节点没有左子树
            if (left[parents[i]] == -1) {
                left[parents[i]] = i;
            } else {
                right[parents[i]] = i;
            }
        }
        dfs(0);
        return cnt;
    }

    //按后续遍历 左右根 返回以此节点为根节点的子树的大小
    private static long dfs(int node) {
        if (node == -1) {
            return 0;
        }
        //dfs获取左右子树的大小
        long leftSize = dfs(left[node]);
        long rightsize = dfs(right[node]);
        //计算三个连通块的乘积
        long score = Math.max(leftSize, 1) * Math.max(rightsize, 1) * Math.max(n - leftSize - rightsize - 1, 1);
        //若乘积等于最大乘积;则记录最大乘积个数的cnt进行加加
        if (score == maxScore) {
            cnt++;
        } else if (score > maxScore) {
            maxScore = score;//若乘积大于最大乘积 cnt更新为1
            cnt = 1;
        }
        return leftSize + rightsize + 1;//返回以此节点为根节点的子树大小(包括自身)
    }

    public static void main1(String[] args) {
        int[] parents = {-1, 2, 0, 2, 0};
        System.out.println(countHighestScoreNodes(parents));
    }

    //牛客 完全数计算 一个树除去自身以外的约数之和等于自身 例如28 约数有1 2 4 7 14 28 除去28之外
    //1 + 2 + 4 + 7+ 14 = 28 所以28为完全数
    public static void main2(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int count = 0;
        for (int i = 2; i <= n; i++) {
            int sum = 0;
            for (int j = 1; j <= Math.sqrt(i); j++) {
                if (i % j == 0) {
                    sum += j;
                    if (i / j != j && j != 1) {
                        sum += (i / j);
                    }
                }
            }
            if (sum == i) {
                count++;
            }
        }
        System.out.println(count);
    }
    //扑克牌大小
    public static void main3(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("3", 1);
        map.put("4", 2);
        map.put("5", 3);
        map.put("6", 4);
        map.put("7", 5);
        map.put("8", 6);
        map.put("9", 7);
        map.put("10", 8);
        map.put("J", 9);
        map.put("Q", 10);
        map.put("K", 11);
        map.put("A", 12);
        map.put("2", 13);
        map.put("joker", 14);
        map.put("JOKER", 15);
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String card = scanner.nextLine();
            String[] cards = card.split("-");
            String[] card1 = cards[0].split(" ");
            String[] card2 = cards[1].split(" ");
            //有王炸出王炸
            if (card.contains("joker JOKER")) {
                System.out.println("joker JOKER");
            } else {
                //除了炸弹,只有同类型(牌数相同)的牌能比较大小
                //这种情况是一边是炸弹;另一边不是炸弹
                if (card1.length != card2.length) {
                    if (card2.length == 4){
                        System.out.println(cards[1]);
                    }else if (card1.length == 4){
                        System.out.println(cards[0]);
                    }else {
                        System.out.println("ERROR");
                    }
                }else {//若牌数相同;无论是个子 对子 三个 顺子还是炸弹;比较第一个牌的大小即可
                    if (map.get(card1[0]) > map.get(card2[0])){
                        System.out.println(cards[0]);
                    }else {
                        System.out.println(cards[1]);
                    }
                }
            }
        }
    }
}
